package linkedlist;

/**
 * @author justnow
 * Created on 2020-10-07
 * Description
 *
 * 反转链表：
 * 反转从位置n到m的链表，请使用一趟扫描完成
 *
 * 第一步：找到待反转节点的前一个节点
 * 第二步：反转m到n这部分
 * 第三步：将反转的起点的next指向翻转后面的一部分
 * 第四步：将第一步找到的节点指向反转以后的头节点
 */
public class Leetcode92 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummpy = new ListNode(-1);
        dummpy.next = head;
        ListNode current = dummpy;
        for (int i = 1; i < m; i++) {
            current.next = current;
        }
        ListNode nextHead = current.next;
        ListNode next = null;
        ListNode pre = null;
        for (int i = m; i <= n; i++) {
            next = nextHead.next;
            nextHead.next = pre;
            pre = nextHead;
            nextHead = next;
        }
        current.next.next = next;
        current.next = pre;
        return dummpy.next;
    }
}
